package epam.com.rd.MyCollections;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList implements MyList, MyQueue, MyStack {

	private int size = 0;

	private static class Node {
		Object item;
		Node next;
		Node prev;

		Node(Node prev, Object element, Node next) {
			this.item = element;
			this.next = next;
			this.prev = prev;
		}
	}

	private Node first;

	private Node last;

	Node node(int index) {

		if (index < (size / 2)) {
			Node x = first;
			for (int i = 0; i < index; i++)
				x = x.next;
			return x;
		} else {
			Node x = last;
			for (int i = size - 1; i > index; i--)
				x = x.prev;
			return x;
		}
	}

	public MyLinkedList() {
	}

	public MyLinkedList(MyList m) {
		this();
		addAll(m);
	}

	public boolean addAll(MyList m) {
		return addAll(size, m);
	}

	public boolean addAll(int index, MyList c) {
		if (!(index >= 0 && index <= size))
			throw new MyIndexOutOfBoundsException("Index out of bounds");

		Object[] a = c.toArray();
		int numNew = a.length;
		if (numNew == 0)
			return false;

		Node pred, succ;
		if (index == size) {
			succ = null;
			pred = last;
		} else {
			succ = node(index);
			pred = succ.prev;
		}

		for (Object o : a) {
			Node newNode = new Node(pred, o, null);
			if (pred == null)
				first = newNode;
			else
				pred.next = newNode;
			pred = newNode;
		}

		if (succ == null) {
			last = pred;
		} else {
			pred.next = succ;
			succ.prev = pred;
		}

		size += numNew;
		return true;
	}

	private void linkFirst(Object e) {
		final Node f = first;
		final Node newNode = new Node(null, e, f);
		first = newNode;
		if (f == null)
			last = newNode;
		else
			f.prev = newNode;
		size++;
	}

	private void linkLast(Object e) {
		final Node l = last;
		final Node newNode = new Node(l, e, null);
		last = newNode;
		if (l == null)
			first = newNode;
		else
			l.next = newNode;
		size++;
	}

	private void linkBefore(Object e, Node succ) {
		final Node pred = succ.prev;
		final Node newNode = new Node(pred, e, succ);
		succ.prev = newNode;
		if (pred == null)
			first = newNode;
		else
			pred.next = newNode;
		size++;
	}

	private Object unlink(Node x) {
		final Object element = x.item;
		final Node next = x.next;
		final Node prev = x.prev;

		if (prev == null) {
			first = next;
		} else {
			prev.next = next;
			x.prev = null;
		}

		if (next == null) {
			last = prev;
		} else {
			next.prev = prev;
			x.next = null;
		}

		x.item = null;
		size--;
		return element;
	}

	private Object unlinkFirst(Node f) {
		final Object element = f.item;
		final Node next = f.next;
		f.item = null;
		f.next = null; // help GC
		first = next;
		if (next == null)
			last = null;
		else
			next.prev = null;
		size--;
		return element;
	}

	private Object unlinkLast(Node l) {
		final Object element = l.item;
		final Node prev = l.prev;
		l.item = null;
		l.prev = null;
		last = prev;
		if (prev == null)
			first = null;
		else
			prev.next = null;
		size--;
		return element;
	}

	public void add(Object e) {
		linkLast(e);

	}

	public void addFirst(Object o) {
		linkFirst(o);
	}

	public void addLast(Object o) {
		linkLast(o);
	}

	public Object getFirst() {
		final Node f = first;
		if (f == null)
			throw new NoSuchElementException();
		return f.item;
	}

	public Object getLast() {
		final Node l = last;
		if (l == null)
			throw new NoSuchElementException();
		return l.item;
	}

	public Object removeFirst() {
		final Node f = first;
		if (f == null)
			throw new NoSuchElementException();
		return unlinkFirst(f);
	}

	public Object removeLast() {
		final Node l = last;
		if (l == null)
			throw new NoSuchElementException();
		return unlinkLast(l);
	}

	public void add(int index, Object e) {
		if (!(index >= 0 && index <= size))
			throw new MyIndexOutOfBoundsException("Index out of bounds");
		if (index == size)
			linkLast(e);
		else
			linkBefore(e, node(index));

	}

	public void addAll(Object[] arr) {
		addAll(size, arr);

	}

	public void addAll(int index, Object[] a) {
		if (!(index >= 0 && index <= size))
			throw new MyIndexOutOfBoundsException("Index out of bounds");

		int numNew = a.length;

		Node pred, succ;
		if (index == size) {
			succ = null;
			pred = last;
		} else {
			succ = node(index);
			pred = succ.prev;
		}

		for (Object o : a) {
			Node newNode = new Node(pred, o, null);
			if (pred == null)
				first = newNode;
			else
				pred.next = newNode;
			pred = newNode;
		}

		if (succ == null) {
			last = pred;
		} else {
			pred.next = succ;
			succ.prev = pred;
		}

		size += numNew;
	}

	public Object get(int index) {
		if (!(index >= 0 && index < size))
			throw new MyIndexOutOfBoundsException(
					"Cant get element - wrong index");
		return node(index).item;
	}

	public Object remove(int index) {
		if (!(index >= 0 && index < size))
			throw new MyIndexOutOfBoundsException(
					"Cant get element - wrong index");
		return unlink(node(index));
	}

	public void clear() {
		for (Node x = first; x != null;) {
			Node next = x.next;
			x.item = null;
			x.next = null;
			x.prev = null;
			x = next;
		}
		first = last = null;
		size = 0;
	}

	public boolean isEmpty() {
		if (size == 0)
			return true;
		else
			return false;
	}

	public void set(int index, Object e) {
		if (!(index >= 0 && index < size))
			throw new MyIndexOutOfBoundsException(
					"Cant get element - wrong index");
		Node x = node(index);
		x.item = e;
	}

	public int indexOf(Object o) {
		int index = 0;
		if (o == null) {
			for (Node x = first; x != null; x = x.next) {
				if (x.item == null)
					return index;
				index++;
			}
		} else {
			for (Node x = first; x != null; x = x.next) {
				if (o.equals(x.item))
					return index;
				index++;
			}
		}
		return -1;
	}

	public int size() {
		return size;
	}

	public Object[] toArray() {
		Object[] result = new Object[size];
		int i = 0;
		for (Node x = first; x != null; x = x.next)
			result[i++] = x.item;
		return result;
	}

	public void push(Object o) {
		addFirst(o);
	}

	public Object pop() {
		return removeFirst();
	}

	public void offer(Object o) {
		addLast(o);
	}

	public Object peek() {
		final Node f = first;
		return (f == null) ? null : f.item;
	}

	public Object poll() {
		final Node f = first;
		return (f == null) ? null : unlinkFirst(f);
	}

	public Iterator<Object> iterator() {
		return new Iterator<Object>() {

			private Node lastReturned = null;
			private Node next = first;
			private int nextIndex = 0;

			public boolean hasNext() {
				return nextIndex < size;
			}

			public Object next() {
				if (!hasNext())
					throw new NoSuchElementException();
				lastReturned = next;
				next = next.next;
				nextIndex++;
				return lastReturned.item;
			}

			public void remove() {
				if (lastReturned == null)
					throw new IllegalStateException();

				Node lastNext = lastReturned.next;
				unlink(lastReturned);
				if (next == lastReturned)
					next = lastNext;
				else
					nextIndex--;
				lastReturned = null;
			}

		};
	}

	public Iterator<Object> descendingIterator() {
		return new Iterator<Object>() {

			private Node lastReturned = null;
			private Node next = last;
			private int nextIndex = size;

			public boolean hasNext() {
				return nextIndex > 0;
			}

			public Object next() {
				if (!hasNext())
					throw new NoSuchElementException();

				lastReturned = next;
				next = next.prev;
				nextIndex--;
				return lastReturned.item;
			}

			public void remove() {
				if (lastReturned == null)
					throw new IllegalStateException();
				unlink(lastReturned);
			}
		};
	}

}
